package com.example.question.bt.backtrack1;

import java.util.ArrayList;
import java.util.List;

/**
 * @Date 2023-07-16
 * @Author Jonathan
 * 生成括号问题
 */
public class Code11_22 {

    public static void main(String[] args) {
        Code11_22 code = new Code11_22();
        List<String> list = code.generateParenthesis(2);
        System.out.println(list);
    }

    public List<String> generateParenthesis(int n) {
        List<String> res = new ArrayList<>();
        if (n < 1) {
            return res;
        }
        dfs(n, "", res, 0, 0);
        return res;
    }


    private void dfs(int n, String path, List<String> res, int open, int close) {
        if (open > n || close > open) {
            return;
        }
        if (path.length() == 2 * n) {
            res.add(path);
            return;
        }
        dfs(n, path + "(", res, open + 1, close);
        dfs(n, path + ")", res, open, close + 1);
    }

    private void dfs1(int n, StringBuilder path, List<String> res, int left, int right) {
        if (left > n || right > left) {
            return;
        }
        if (path.length() == 2 * n) {
            res.add(path.toString());
            return;
        }
        boolean leftFlag = false;
        boolean rightFlag = false;
        for (int i = 0; i < 2; i++) {
            if (i == 0) {
                path.append("(");
                leftFlag = true;
            } else {
                path.append(")");
                rightFlag = true;
                leftFlag = false;
                // 栈顶是左括号的时候 就出栈
            }
        }

        dfs1(n, path, res, leftFlag ? (left + 1) : left, rightFlag ? (right + 1) : right);
//        leftFlag = false;
//        rightFlag = false;
        path.deleteCharAt(path.length() - 1);
    }
}
